#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>

using namespace std;
// 15.三数之和
// 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
// 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
// 请你返回所有和为 0 且不重复的三元组。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        assert(nums.size() >= 3);
        // 先进行排序
        sort(nums.begin(), nums.end());

        vector<vector<int>> resultVec;

        for(int i = 0; i < nums.size() - 2; i++) {
            if(i > 0 && nums[i] == nums[i-1]) {
                // 与上一个数相同，直接过滤，可以提升性能
                continue;
            }

            // 确定a和b后，用来存储预期的c
            set<int> tmpSet;
            for(int j = i+1; j < nums.size(); j++) {
                int restToZero = -(nums[i] + nums[j]);
                if(tmpSet.find(nums[j]) != tmpSet.end()) {
                    int arr[] = {nums[i], restToZero, nums[j]};
                    // 当前数值等于预期的c，说明有满足条件值，a是nums[i], b是-(nums[i] + nums[j]), c是nums[j]
                    vector<int> ans = {nums[i], restToZero, nums[j]};
                    resultVec.push_back(ans);
                } else {
                    // 把预期的c存入set
                    tmpSet.insert(restToZero);
                }
            }
        }
        return resultVec;
    }
};

int main() {
    vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = Solution().threeSum(nums1);
    for( int i = 0 ; i < res.size() ; i ++ ){
        for( int j = 0 ; j < res[i].size() ; j ++ )
            cout<<res[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}
